// @algorithm @lc id=221 lang=cpp 
// @title maximal-square


// @test([["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]])=4
// @test([["0","1"],["1","0"]])=1
// @test([["0"]])=0
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if(m == 0 || matrix[0].size() == 0) return 0;
        int n = matrix[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        int ans = 0;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(matrix[i][j]=='0')
                    continue;
                if(i==0 || j==0)
                    dp[i][j] = 1;
                else
                    dp[i][j] = min(dp[i][j-1], min(dp[i-1][j], dp[i-1][j-1])) + 1;
                if(dp[i][j] > ans)
                    ans = dp[i][j];
            }
        }
        return ans*ans;
    }
};